package 剑指offer.堆栈队列;

import java.util.PriorityQueue;

/**
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * <p>
 * 其实一眼看去的解法就是持续不断的给到来的数据排序，然后取中位数。
 * 但是随着数据流的增加，排序的时间会增长到O(n)，因为往中间插入数据要移动其他数据。但是查找只需要 O(1)
 * <p>
 * 一个更好的办法就是使用两个堆分别存储中间数两边的数据，这样时间复杂度就降到 O(lgn)
 */
public class 第41题数据流中的中位数 {

    /*
    将数据流按照中间值分为两部分：小于中间值的、大于中间值的

    为了存储这两边的数据：
        小于中间值的用最大堆（保证堆顶是左边最大的，中间值要大于堆顶，也就是大于左边的全部数据）
        大于中间值的用最小堆（保证堆顶是右边最小的，中间值要小于堆顶，也就是小于右边的全部数据）

     那么就涉及到如何存储数据使得左右两边的数据整体有序？
        1. 为了均衡数据量，获取到偶数个数据时统一放到最小堆。奇数个放到最大堆
        2. num 如何加入到堆里面使得最终结果是排序的：
            1. 把该 num 加入到最大堆，然后把堆顶元素拿出来放到最小堆里面。
            2. 把该 num 加入到最小堆，然后把堆顶元素放入到最大堆里面
     */
    PriorityQueue<Integer> min = new PriorityQueue<>();
    PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2) -> o2 - o1);
    int count = 0;

    public void Insert(Integer num) {
        // 录入的总数据量是奇数放入到最大堆
        if (count % 2 == 0) {
            max.add(num);
            int maxx = max.poll();
            min.add(maxx);
        } else {
            // 偶数。放入最小堆
            min.add(num);
            int minn = min.poll();
            max.add(minn);
        }
        count++;
    }

    public Double GetMedian() {
        if (count % 2 == 0) {
            return new Double(min.peek() + max.peek()) / 2;
        } else {
            return new Double(min.peek());
        }
    }


}
